//
// Created by 123 on 2024/4/1.
//
/**
 * 希尔排序
 *      所谓的希尔排序，就是利用插入排序的特性：
 *          当序列大致上有序时，插入排序效率高
 *      思想：将整个序列分为 step份 初始 step=length
 *          在每一份中用直接插入排序
 *          全部结束后，step除2 直到 step为1为止
 *
 *      [O(n^1.3),O(n^2)]
 */
#include <iostream>

using namespace std;

#define MaxSize 100

typedef struct Array {
    int data[MaxSize];
    int length;
} Array, *Arr;

Array *initArray(int arr[], int len);

void swap(int &a, int &b);


void shell_sort(Arr &arr);


int main() {
    int a[10]{49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    Arr arr = initArray(a, 10);
    shell_sort(arr);
    for (int i = 0; i < arr->length; ++i) {
        cout << arr->data[i] << "    ";
    }
}

void shell_sort(Arr &arr) {
//    下标从 1 开始，默认0有序
    int step = arr->length / 2;
    while (step >=1) {
        for (int i = 0; i < step; ++i) {
            for (int j = i+step; j< arr->length; j = j + step) {
                int data=arr->data[j]
                if(arr->data[j-step]>data){
                    int k=j;
                    for ( k ; k >i&&arr->data[k-step]>data ; k=k-step) {
                        arr->data[k]=arr->data[k-step];
                    }
                    arr->data[k]=data;
                }

            }
        }
        step = step / 2;
    }
}


Array *initArray(int arr[], int len) {
    Arr array = (Array *) malloc(sizeof(Array));
    for (int i = 0; i < len; ++i) {
        array->data[i] = arr[i];
    }
    array->length = len;
    return array;
}

void swap(int &a, int &b) {
    int turn = a;
    a = b;
    b = turn;
}